// Filename:  List.hpp
// Created:  05/16/2011 11:05:32 AM
#ifndef LIST_HPP
#define LIST_HPP

#include "Allocator.h"
#include "Iterator.h"

class OutOfRange {
};

class LengthError {

};

template <typename T>
struct ListNode {
	T		elem;
	ListNode<T>*	next;
	ListNode<T>*	prev;
};

#ifndef NULL
#define NULL ((void *)0)
#endif


template <class T>
class ListIterator : public Iterator<BidirectionalIteratorTag, T>
{
	ListNode<T> * p;
public:
	ListIterator() : p(0) {}
	ListIterator( ListNode<T> *  x) : p(x) {}
	ListIterator(const ListIterator & b) : p(b.p) {}
	ListIterator & operator=(const ListIterator & b) { p = b.p; return *this;}
	bool operator== (const ListIterator & b) const { return (p == b.p); }	
	bool operator!= (const ListIterator & b) const { return !operator==(b); }
	T& operator* () 
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}

	T operator* () const
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}
	T * operator->()
	{
		if (p)
			return &p->elem;
		throw OutOfRange();
	}

	ListIterator& operator++() 
	{
		if (p)
			p = p->next;
		return *this;
	}


	ListIterator& operator--()
	{	
		if (p)
			p = p->prev;
		return *this;
	}

	ListIterator operator++(int) 
	{
		ListIterator tmp(*this);
		operator++();
		return tmp;
	}
	ListIterator operator--(int)
	{
		ListIterator tmp(*this);
		operator--();
		return tmp;
	}	


	template <typename TT, typename Alloc> friend class List;	
	
};


template <class T>
class ConstListIterator : public Iterator<BidirectionalIteratorTag, T>
{
	const ListNode<T> * p;
public:
	ConstListIterator() : p(0) {}
	ConstListIterator( const ListNode<T> *  x) : p(x) {}
	ConstListIterator(const ConstListIterator & b) : p(b.p) {}
	const ConstListIterator & operator=(const ConstListIterator & b) { p = b.p; return *this;}
	bool operator== (const ConstListIterator & b) const { return (p == b.p); }	
	bool operator!= (const ConstListIterator & b) const { return !operator==(b); }
	const T& operator* () 
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}

	T operator* () const
	{
		if (p)
			return  p->elem;
		throw OutOfRange();
	}
	T * operator->() const 
	{
		if (p)
			return &p->elem;
		throw OutOfRange();
	}

	ConstListIterator& operator++() 
	{
		if (p)
			p = p->next;
		return *this;
	}


	ConstListIterator& operator--()
	{	
		if (p)
			p = p->prev;
		return *this;
	}

	ConstListIterator operator++(int) 
	{
		ConstListIterator tmp(*this);
		operator++();
		return tmp;
	}
	ConstListIterator operator--(int)
	{
		ConstListIterator tmp(*this);
		operator--();
		return tmp;
	}			
};

template <typename T>
class ListReverseIterator : public Iterator<BidirectionalIteratorTag, T>
{
	T * p;
public:
	ListReverseIterator() : p(0) {}
	ListReverseIterator( ListNode<T> * x) : p(x) {}
	ListReverseIterator(const ListReverseIterator & b) : p(b.p) {}
	ListReverseIterator & operator=(const ListReverseIterator & b) { p = b.p; return *this;}
	bool operator== (const ListReverseIterator & b) { return (p == b.p); }	
	bool operator!= (const ListReverseIterator & b) { return !operator==(b); }
	T& operator* () 
	{
		if (p)
			return p->elem;
		throw OutOfRange();
	}
	T * operator->()
	{
		if (p)
			return &p->elem;
		throw OutOfRange();
	}
	ListReverseIterator& operator++() 
	{
		if (p)
			p = p->prev;
		return *this;
	}
	ListReverseIterator& operator--()
	{	
		if (p)
			p = p->next;
		return *this;
	}
	ListReverseIterator operator++(int) 
	{
		ListReverseIterator tmp(*this);
		operator++();
		return tmp;
	}
	ListReverseIterator operator--(int)
	{
		ListReverseIterator tmp(*this);
		operator--();
		return tmp;
	}	
};

template <typename T, typename Alloc = Allocator<T>  > 
class List {

public:
	typedef typename Alloc::reference reference;
	typedef typename Alloc::const_reference const_reference;
	typedef typename Alloc::size_type size_type;
	typedef typename Alloc::difference_type difference_type;
	typedef	typename Alloc::value_type value_type;
	typedef typename Alloc::pointer pointer;
	typedef typename Alloc::const_pointer const_pointer;

	typedef	Alloc		allocator_type;
	typedef	ListNode<T>	Node;
	typedef	Node *		nodePtr;

	typedef ListIterator<T> iterator;
	typedef ConstListIterator<T>	const_iterator;
	typedef ListReverseIterator<T> reverse_iterator;
	typedef const ListReverseIterator<T> const_reverse_iterator;
	
	explicit List ( const Alloc& = Alloc() ) : head(0), tail(0), len(0) { }
	explicit List ( size_type n, const T& value = T(), const Alloc& = Alloc() );
	template < class InputIterator >
	List ( InputIterator first, InputIterator last, const Alloc& = Alloc() );
	List ( const List<T,Alloc>& x );	
	~List () {
		freeList(head);
	}

	template <class InputIterator>
	  void assign ( InputIterator first, InputIterator last );
	void assign ( size_type n, const T& u );

	bool empty ( ) const
	{
		return (len == 0);
	}

	size_type size() const	
	{
		return len;
	}
	size_type max_size () const
	{
		return nodeAlloc.max_size();
	}

	iterator begin ()
	{
		return (head);
	}
	const_iterator begin () const	
	{
		return (const ListNode<T> * ) head;
	}

	iterator end ()
	{
		return (nodePtr)NULL;
	}
	const_iterator end () const
	{
		return (const nodePtr)NULL;
	}

      	reference front ()
	{
		if (head == NULL)
			throw OutOfRange();
		return head->elem;
	}
	const_reference front () const
	{
		if (head == NULL)
			throw OutOfRange();
		return head->elem;
	}

	reference back ( )
	{
		if (tail == NULL)
			throw OutOfRange();	
		return tail->elem;
	}

	const_reference back ( ) const
	{
		if (tail == NULL)
			throw OutOfRange();	
		return tail->elem;
	} 

	void push_front ( const T& x )
	{
		nodePtr cur = newNode(x);
		assert(cur != NULL);
		insertNode(head, cur);
		head = cur;
		if (tail == NULL)
			tail = cur;
	}
	
	void pop_front ()
	{
		if (head == NULL)
			throw OutOfRange();
		deleteNode(head);
	}

	void push_back ( const T& x )
	{
		nodePtr cur = newNode(x);
		assert(cur != NULL);
		appendNode(tail, cur);
		tail = cur;
		if (head == NULL)
			head = cur;
	}
	void pop_back ()
	{
		if (tail == NULL)
			throw OutOfRange();
		deleteNode(tail);
	}
		
	iterator erase(iterator position)
	{
		nodePtr ret = NULL;
		if (position != end())
			ret = deleteNode(position.p);
		return (iterator) ret;
	}

	iterator erase(iterator first, iterator last)
	{
		nodePtr ptr = first.p;
		for (; ptr != last.p; )	
			ptr = deleteNode(ptr);
		return (iterator)ptr;
	}
	

private:
	allocator_type	alloc;
	nodePtr		head;
	nodePtr		tail;
	size_type 	len;
	Allocator<Node> nodeAlloc;
	
	nodePtr newNode(const T & value = T())
	{
		nodePtr cur = nodeAlloc.allocate(1);
		alloc.construct(&cur->elem, value);
		cur->next = cur->prev = NULL;
		return cur;
	}

	nodePtr insertNode(nodePtr ptr, nodePtr cur)
	{		
		cur->next = ptr;
		if (ptr && ptr->prev != NULL)
		{
			cur->prev = ptr->prev;
			ptr->prev->next = cur;
		}

		if (ptr)
			ptr->prev = cur;

		if (ptr == NULL)
			cur->prev = ptr;
		++len;

		return cur;
	}
	
	nodePtr appendNode(nodePtr ptr, nodePtr cur)
	{
		cur->next = NULL;
		cur->prev = ptr;
		if (ptr != NULL)
			ptr->next = cur;		
		++len;

		return cur;
	}


	nodePtr deleteNode(nodePtr cur )
	{
		if (cur->prev == NULL)
		{
			head = cur->next;
		}
		else
			cur->prev->next = cur->next;

		if (cur->next == NULL)
		{
			tail = cur->prev;
		}
		else
			cur->next->prev = cur->prev;

		nodePtr ret = cur->next;
		alloc.destroy(&cur->elem);		
		nodeAlloc.deallocate(cur, 1);
		--len;

		return ret;
	}
	
	void freeList(const nodePtr & beg, const nodePtr & end = (nodePtr)NULL)
	{
		for (nodePtr ptr = beg; ptr != end; )
			ptr = deleteNode(ptr);
	}

};


template <typename T, typename Alloc > 
inline List<T, Alloc>::List ( size_type n, const T& value, const Alloc& ): head(0), tail(0), len(0) 
{
	assign(n, value);
}

template <typename T, typename Alloc > 
template < class InputIterator >
inline List<T, Alloc>::List ( InputIterator first, InputIterator last, const Alloc& ) : head(0), tail(0), len(0)
{
	assign(first, last);
}

template <typename T, typename Alloc > 
inline List<T, Alloc>::List ( const List<T,Alloc>& x ) : head(0), tail(0), len(0)
{
	assign(x.begin(), x.end());
}

template <typename T, typename Alloc > 
template <class InputIterator>
  void List<T, Alloc>::assign ( InputIterator first, InputIterator last )
{
	nodePtr tmpHead = NULL;
	nodePtr tmpTail = NULL;
	InputIterator it = first;

	for (; it != last; ++it)
	{
		nodePtr cur = newNode(*it);
		assert(cur != NULL);
		appendNode(tmpTail,  cur);
		if (it == first)
			tmpHead = cur;
		tmpTail = cur;
	}
	if (head != NULL)
	{
		freeList(head);
		head = NULL;
		tail = NULL;
	
	}
	head = tmpHead;
	tail = tmpTail;
}

template <typename T, typename Alloc > 
void List<T, Alloc>::assign ( size_type n, const T& u )
{
	nodePtr tmpHead = NULL;
	nodePtr tmpTail = NULL;

	for(size_type i = 0; i < n; ++i)
	{
		nodePtr cur = newNode(u);
		assert(cur != NULL);

		appendNode(tmpTail,  cur);
		if (i == 0)
			tmpHead = cur;
		tmpTail = cur;
	}
	if (head != NULL)
	{
		freeList(head);
		head = NULL;
		tail = NULL;
	
	}
	head = tmpHead;
	tail = tmpTail;

}

	
#endif
